package cn.arts.assumejson.algo.sort.class01;

/**
 * <a href="https://leetcode.cn/problems/find-in-mountain-array/">FindInMountainArray</a>
 *
 * @author by <a href="mailto:ligang941012@gmail.com">gang.Li</a>
 * @since 2024/9/9 22:45
 */
public class FindInMountainArrayFrom1095 {
    public int findInMountainArray(int target, MountainArray mountainArr) {
        int L = 0, R = mountainArr.length() - 1;
        int topPeak = findMountainPeak(mountainArr);
        if (mountainArr.get(topPeak) == target) return topPeak;
        else if (mountainArr.get(topPeak) < target) return -1;
        else {
            int index = findLeftTarget(mountainArr, L, topPeak - 1, target);
            return index != -1 ? index : findRightTarget(mountainArr, topPeak + 1, R, target);
        }
    }

    public int findRightTarget(MountainArray mountainArray, int L, int R, int target) {
        int mid;
        while (L <= R) {
            mid = L + ((R - L) >> 1);
            if (mountainArray.get(mid) == target) return mid;
            else if (mountainArray.get(mid) > target) {
                L = mid + 1;
            } else {
                R = mid - 1;
            }
        }
        return -1;
    }

    public int findLeftTarget(MountainArray mountainArray, int L, int R, int target) {
        int mid;
        while (L <= R) {
            mid = L + ((R - L) >> 1);
            if (mountainArray.get(mid) == target) {
                return mid;
            } else if (mountainArray.get(mid) > target) {
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
        return -1;
    }

    public int findMountainPeak(MountainArray mountainArray) {
        int L = 0, mid, R = mountainArray.length() - 1;
        while (L < R) {
            mid = L + ((R - L) >> 1);
            if (mountainArray.get(mid) < mountainArray.get(mid + 1)) {
                L = mid + 1;
            } else {
                R = mid;
            }
        }
        return L;
    }

    interface MountainArray {
        int get(int k);

        int length();
    }
}
